package day_2022_9_to_12.Day;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author haomin
 * @date 2022/09/23 22:24
 **/
public class Day22_4_Num116_Connect {
    class Node {
        public int val;
        public Node left;
        public Node right;
        public Node next;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _left, Node _right, Node _next) {
            val = _val;
            left = _left;
            right = _right;
            next = _next;
        }
    };
    class Solution1 {
        public Node connect(Node root) {
            if(root == null) return null;
            if(root.left != null){
                root.left.next = root.right;
                if(root.next != null){
                    root.right.next = root.next.left;
                }
            }
            connect(root.left);
            connect(root.right);
            return root;
        }
    }

    class Solution {
        public Node connect(Node root) {
            if(root == null) return null;
            Queue<Node> q = new LinkedList<>();
            q.offer(root);
            while(!q.isEmpty()){
                int size = q.size();
                for(int i = 0; i < size; ++i){
                    Node cur = q.poll();
                    if(i + 1 != size){
                        cur.next = q.peek();
                    }
                    if(cur.left != null) q.offer(cur.left);
                    if(cur.right != null) q.offer(cur.right);
                }
            }
            return root;
        }
    }
}